class Solution(object):
    def distinctSubseqII(self, s):
        n = len(s)
        p = [-1] * n
        d = {}
        base = 10 ** 9 + 7
        for index, c in enumerate(s):
            if c in d:
                p[index] = d[c]
            else:
                p[index] = -1
            d[c] = index
        DP = [0] * n
        DP[0] = 1
        for i in range(1, n):
            last = p[i]
            if last == 0:
                DP[i] = (2 * DP[i - 1]) % base
            else:
                if last == -1:
                    DP[i] = (2 * DP[i - 1] + 1) % base
                else:
                    DP[i] = (2 * DP[i - 1] - DP[i - 2]) % base
        return DP[-1]
